package arithmetic;

import utils.PrintUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: Jie
 * @Date: 2019/2/12 11:01
 * @Function :22. 括号生成
 * 一个循环 产生所有可能。1-->n   1-->2n
 */
public class A_15_GenerateParenthesis {
    public static void main(String[] args) {
        List<String> strings = generateParenthesis(3);
        PrintUtil.print(strings);
        //eg:2   (()),()(),
        /**
         *   open:0  close0
         * (  open:1  close0
         * ((  open:2  close0
         * (()  open:2  close1
         * (())  open:2  close2
         * ()  open:1  close1
         * ()(  open:2  close1
         * ()()  open:2  close2
         */
        //eg:3  ((())),(()()),(())(),()(()),()()(),
        /**
         *   open:0  close0
         * (  open:1  close0
         * ((  open:2  close0
         * (((  open:3  close0
         * ((()  open:3  close1
         * ((())  open:3  close2
         * ((()))  open:3  close3
         * (()  open:2  close1
         * (()(  open:3  close1
         * (()()  open:3  close2
         * (()())  open:3  close3
         * (())  open:2  close2
         * (())(  open:3  close2
         * (())()  open:3  close3
         * ()  open:1  close1
         * ()(  open:2  close1
         * ()((  open:3  close1
         * ()(()  open:3  close2
         * ()(())  open:3  close3
         * ()()  open:2  close2
         * ()()(  open:3  close2
         * ()()()  open:3  close3
         */
    }

    public static List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        backtrack(ans,"",0,0,n);
        return  ans;
    }

    //回溯法
    /**
     * 序列仍然保持有效时才添加 '(' or ')'
     * @param ans
     * @param s
     * @param open
     * @param close
     * @param n
     */
    private static void backtrack(List<String> ans, String s, int open, int close, int n) {
        System.out.println(s+"  open:"+open+"  close"+close);
        if (s.length()==n*2){
          ans.add(s);
        } else {
            if (open<n){
                backtrack(ans,s+"(",open+1,close,n);
            }
            if (close<open){
                backtrack(ans,s+")",open,close+1,n);
            }
        }
    }
}
